package algorithm.bin_tree.depthtraverse;

import algorithm.bin_tree.BinTree;
import algorithm.bin_tree.Node;

import java.util.List;
import java.util.Stack;

/**
 * @program: util
 * @description:
 * @author: zhouliangliang
 * @create: 2021-06-04 20:38
 **/
public class PostRootDepthTraverse {

    /**
     * 递归后根遍历
     * @param root
     */
    public void postHeadTraversal(Node root) {
        if( null == root) {
            return;
        }
        postHeadTraversal(root.leftChild);
        postHeadTraversal(root.rightChild);
        System.out.print(root.data + " ");
    }

    /**
     * 非递归，使用堆栈的后根遍历
     * @param root
     */
    public void postOrderTraversal(Node root) {
        if (root == null) return;

        Stack<Node> stack = new Stack<>();
        Stack<Node> output = new Stack<>(); // 用于反转访问顺序
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            output.push(node); // 先访问的节点后输出

            // 左子树先入栈（后访问）
            if (node.leftChild != null) {
                stack.push(node.leftChild);
            }
            // 右子树后入栈（先访问）
            if (node.rightChild != null) {
                stack.push(node.rightChild);
            }
        }

        // 输出结果（后序遍历顺序）
        while (!output.isEmpty()) {
            System.out.print(output.pop().data + " ");
        }
    }

    public static void main(String[] args) {
        BinTree tree = new BinTree();
        int[] array = new int[]{1,2,3,4,5,6,7};
        List<Node> list = tree.createBinTree(array);

        PostRootDepthTraverse prt = new PostRootDepthTraverse();
        prt.postOrderTraversal(list.get(0));
        prt.postHeadTraversal(list.get(0));

    }
}
